Manolis Zampetakis

Welcome! I am currently an assistant professor of Computer Science at Yale University.

Before Yale, I was a postdoc at the EECS Department of UC Berkeley working with Michael Jordan.

I received my PhD from the EECS Department at MIT where I was very fortunate to be advised by Constantinos Daskalakis. For my thesis, I was awared the ACM SIGEcom Doctoral Dissertation Award. In fall 2018, I received the Google PhD Fellowship.

I completed my undergraduate studies at NTUA where I was fortunate to work with Dimitris Fotakis.

My research interests include: Theoretical Machine Learning, Statistics, Optimization, Computational Complexity, Game Theory, Mechanism Design.

Email: manolis.zampetakis [at) yale(dot]edu

Students

Under Preparation

Published Papers

    2025
  1. On the Hardness of Learning One Hidden Layer Neural Networks
    with Shuchen Li, Ilias Zadik
    ALT 2025 • 36th International Conference on Algorithmic Learning Theory
    2. 2024
  2. Smaller Confidence Intervals From IPW Estimators via Data-Dependent Coarsening
    with Alkis Kalavasis, Anay Mehrotra
    COLT 2024 • 37th Annual Conference on Learning Theory
  3. Efficient Statistics With Unknown Truncation, Polynomial Time Algorithms, Beyond Gaussians
    with Jane H. Lee, Anay Mehrotra
    FOCS 2024 • 65th IEEE Symposium on Foundations of Computer Science
  4. Imperfect-Recall Games: Equilibrium Concepts and Their Complexity
    with Emanuel Tewolde, Brian Hu Zhang, Tuomas Sandholm, Caspar Oesterheld, Paul Goldberg, Vincent Conitzer
    IJCAI 2024 • 33rd International Joint Conference on Artificial Intelligence
  5. On the Complexity of Computing Sparse Equilibria and Lower Bounds for No-Regret Learning in Games
    with Ioannis Anagnostides, Alkis Kalavasis, Tuomas Sandholm
    ITCS 2024 • 16th Innovations in Theoretical Computer Science
  6. Injecting Undetectable Backdoors in Obfuscated Neural Networks and Language Models
    with Alkis Kalavasis, Amin Karbasi, Argyris Oikonomou, Katerina Sotiraki, Grigoris Velegkas
    NeurIPS 2024 • 38th Annual Conference on Neural Information Processing Systems
  7. Tree of Attacks: Jailbreaking Black-Box LLMs Automatically
    with Anay Mehrotra, Paul Kassianik, Blaine Nelson, Yaron Singer, Amin Karbasi
    NeurIPS 2024 • 38th Annual Conference on Neural Information Processing Systems
    8. 2023
  8. The Computational Complexity of Finding Stationary Points in Non-Convex Optimization
    with Alexandros Hollender
    COLT 2023 • 36th Annual Conference on Learning Theory
  9. Deterministic Nonsmooth Nonconvex Optimization
    with Michael I. Jordan, Guy Kornowski, Ohad Shamir, and Tianyi Lin
    COLT 2023 • 36th Annual Conference on Learning Theory
  10. STay-ON-the-Ridge: Guaranteed Convergence to Min-Max Critical Points in Nonconvex-Nonconcave Games
    with Constantinos Daskalakis, Noah Golowich and Stratis Skoulakis
    COLT 2023 • 36th Annual Conference on Learning Theory
  11. Smoothed Analysis of Online Non-parametric Auctions
    with Naveen Durvasula and Nika Haghtalab
    EC 2023 • 24th ACM Conference on Economics and Computation
  12. The Computational Complexity of Multi-player Concave Games and Kakutani Fixed Points
    with Christos Papadimitriou and Manolis Vlatakis
    EC 2023 • 24th ACM Conference on Economics and Computation
  13. What Makes a Good Fisherman? Linear Regression under Self-Selection Bias
    with Yeshwanth Cherapanamjeri, Constantinos Daskalakis and Andrew Ilyas
    STOC 2023 • 55th ACM Symposium on Theory of Computing
  14. Last-Iterate Convergence of Saddle Point Optimizers via High-Resolution Differential Equations
    with Tatjana Chavdarova and Michael I. Jordan
    MTA • Minimax Theory and its Applications, Volume 8 (2023)
    Preliminary version: Optimization for Machine Learning Workshop @ NeurIPS 2021
  15. Bayesian Strategy-Proof Facility Location via Robust Estimation
    with Fred Zhang
    AISTATS 2023 • 26th International Conference on Artificial Intelligence and Statistics
    16. 2022
  16. Learning and Covering Sums of Independent Random Variables with Unbounded Support
    with Alkis Kalavasis and Konstantinos Stavropoulos
    NeurIPS 2022 • 36th Conference on Neural Information Processing Systems Oral
  17. First-Order Algorithms for Nonlinear Generalized Nash Equilibrium Problems
    with Michael I. Jordan and Tianyi Lin
    JMLR • Journal of Machine Learning Research, Volume 24 (2023)
  18. Estimation of Standard Auction Models
    with Yeshwanth Cherapanamjeri, Constantinos Daskalakis and Andrew Ilyas
    EC 2022 • 23rd ACM Conference on Economics and Computation
    Preliminary version: Learning and Decision-Making with Strategic Feedback @ NeurIPS 2021 Spotlight
    19. 2021
  19. Robust Learning of Optimal Auctions
    with Wenshuo Guo and Michael I. Jordan
    NeurIPS 2021 • 35th Conference on Neural Information Processing Systems Spotlight
  20. Private and Non-private Uniformity Testing for Ranking Data
    with Róbert Busa-Fekete and Dimitris Fotakis
    NeurIPS 2021 • 35th Conference on Neural Information Processing Systems
  21. Identity testing for Mallows model
    with Róbert Busa-Fekete, Dimitris Fotakis and Balázs Szörényi
    NeurIPS 2021 • 35th Conference on Neural Information Processing Systems
  22. Efficient Truncated Linear Regression with Unknown Noise Variance
    with Constantinos Daskalakis, Patroklos Stefanou and Rui Yao
    NeurIPS 2021 • 35th Conference on Neural Information Processing Systems
  23. A Statistical Taylor Theorem and Extrapolation of Truncated Densities
    with Constantinos Daskalakis, Vasilis Kontonis, and Christos Tzamos
    COLT 2021 • 34th Annual Conference on Learning Theory
  24. The Complexity of Constrained Min-Max Optimization
    with Constantinos Daskalakis and Stratis Skoulakis
    STOC 2021 • 53rd Annual ACM Symposium on Theory of Computing
  25. A Topological Characterization of Modulo-p Arguments and Implications for Necklace Splitting
    with Aris Filos-Ratsikas, Alexandros Hollender and Katerina Sotiraki
    SODA 2021 • 32nd ACM-SIAM Symposium on Discrete Algorithms
    26. 2020
    Ph.D. Thesis • Statistics in High Dimensions without IID Samples:
    Truncated Statistics and Minimax Optimization
    ACM SIGEcom Doctoral Dissertation Award
  26. Constant-Expansion Suffices for Compressed Sensing with Generative Priors
    with Constantinos Daskalakis and Dhruv Rohatgi
    NeurIPS 2020 • 34th Conference on Neural Information Processing Systems Spotlight
  27. Optimal Approximation - Smoothness Tradeoffs for Soft-Max Functions
    with Alessandro Epasto, Mohammad Mahdian and Vahab Mirrokni
    NeurIPS 2020 • 34th Conference on Neural Information Processing Systems Spotlight
    Preliminary version: Learning in Presence of Strategic Behavior Workshop @ EC 2019
  28. Truncated Linear Regression in High Dimensions
    with Constantinos Daskalakis and Dhruv Rohatgi
    NeurIPS 2020 • 34th Conference on Neural Information Processing Systems
  29. Estimation and Inference with Trees and Forests in High Dimensions
    with Vasilis Syrganis
    COLT 2020 • 33rd Annual Conference on Learning Theory
  30. More Revenue from Two Samples via Factor Revealing SDPs
    with Constantinos Daskalakis
    EC 2020 • 21st ACM Conference on Economics and Computation
  31. Consensus-Halving: Does it Ever Get Easier?
    with Aris Filos-Ratsikas, Alexandros Hollender and Katerina Sotiraki
    EC 2020 • 21st ACM Conference on Economics and Computation
  32. On the Complexity of Modulo-q Arguments and the Chevalley-Warning Theorem
    with Mika Göös, Pritish Kamath and Katerina Sotiraki
    CCC 2020 • 35th Computational Complexity Conference
  33. A Theoretical and Practical Framework for Regression and Classification from
          Truncated Samples
    with Costantinos Daskalakis, Andrew Ilyas
    AISTATS 2020 • 23rd International Conference on Artificial Intelligence and Statistics
    34. 2019
  34. Efficient Truncated Statistics with Unknown Truncation
    with Vasilis Kontonis, and Christos Tzamos
    FOCS 2019 • 60th Annual IEEE Symposium on Foundations of Computer Science
  35. Computationally and Statistically Efficient Truncated Regression
    with Constantinos Daskalakis, Themis Gouleakis and Christos Tzamos
    COLT 2019 • 32nd Conference on Learning Theory
  36. Optimal Learning of Mallows Block Model
    with Róbert Busa-Fekete, Dimitris Fotakis and Balázs Szörényi
    COLT 2019 • 32nd Conference on Learning Theory
    37. 2018
  37. Efficient Statistics, in High Dimensions, from Truncated Samples
    with Constantinos Daskalakis, Themis Gouleakis and Christos Tzamos
    FOCS 2018 • 59th Annual IEEE Symposium on Foundations of Computer Science
  38. PPP-completeness with Connections to Cryptography
    with Katerina Sotiraki and Giorgos Zirdelis
    FOCS 2018 • 59th Annual IEEE Symposium on Foundations of Computer Science
  39.   Certified Computation from Unreliable Datasets
    with Themis Gouleakis and Christos Tzamos
    COLT 2018 • 31th Conference on Learning Theory
  40.   A Converse to Banach's Fixed Point Theorem and its CLS Completeness
    with Constantinos Daskalakis and Christos Tzamos
    STOC 2018 • 50th Annual ACM Symposium on the Theory of Computing
  41.   Bootstrapping EM via Power EM and Convergence in the Naive Bayes Model
    with Constantinos Daskalakis and Christos Tzamos
    AISTATS 2018 • 21st International Conference on Artificial Intelligence and Statistics
    42. 2017
  42.   Ten Steps of EM Suffice for Mixtures of Two Gaussians
    with Constantinos Daskalakis and Christos Tzamos
    COLT 2017 • 30th Conference on Learning Theory
    Preliminary version: NIPS Workshop on Non-Convex Optimization for Machine Learning, 2016.
  43.   Faster Sublinear Algorithms using Conditional Sampling
    with Themis Gouleakis and Christos Tzamos
    SODA 2017 • 28th ACM-SIAM Symposium on Discrete Algorithms
    44. 2013 - 2016
  44.   Mechanism Design with Selective Verification
    with Dimitris Fotakis and Christos Tzamos
    EC 2016 • 17th ACM Economics and Computation
  45.   Efficient Money Burning in General Domains
    with Dimitris Fotakis , Dimitris Tsipras and Christos Tzamos
    SAGT 2015 • 8th International Symposium on Algorithmic Game Theory Special Issue
  46.   Scheduling MapReduce Jobs and Data Shuffle on Unrelated Processors
    with Dimitris Fotakis , Ioannis Milis , Orestis Papadigenopoulos and Giorgos Zois
    SEA 2015 • 14th International Symposium on Experimental Algorithms
    Preliminary version: EDBT/ICDT Workshop on Algorithms for Map Reduce and Beyond, 2014.
  47.   Truthfulness Flooded Domains and the Power of Verification for Mechanism Design
    with Dimitris Fotakis
    WINE 2013 • 9th Conference on Web and Internet Economics Special Issue

Awards

Service